// https://leetcode.cn/problems/regular-expression-matching/

// 算法思路总结：
// 1. 动态规划解决正则表达式匹配问题
// 2. 处理三种模式字符：普通字母、'.'通配符、'*'重复符
// 3. '*'的处理：匹配0次（跳过组合）或匹配1+次（字符相等时继续使用）
// 4. 初始化：空模式匹配空串，'*'组合可匹配空字符串
// 5. 时间复杂度：O(m×n)，空间复杂度：O(m×n)

#include <iostream>
using namespace std;

#include <vector>
#include <string>
#include <algorithm>

class Solution 
{
public:
    bool isMatch(string s, string p) 
    {
        int m = s.size(), n = p.size();
        s = " " + s, p = " " + p;

        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));

        dp[0][0] = true;
        for (int j = 2 ; j <= n ; j += 2)
        {
            if (p[j] == '*')
            {
                dp[0][j] = true;
            }
            else break;
        }

        for (int i = 1 ; i <= m ; i++)
        {
            for (int j = 1; j <= n ; j++)
            {
                if (isalpha(p[j]) && s[i] == p[j])
                {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else if (p[j] == '.')
                {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else if (p[j] == '*')
                {
                    if (p[j - 1] == '.')
                    {
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                    }
                    else 
                    {
                        dp[i][j] = dp[i][j - 2] || (s[i] == p[j - 1] && dp[i - 1][j]);
                    }
                }           
            }
        }

        return dp[m][n];
    }
};

int main()
{
    string s1 = "aa", p1 = "a";
    string s2 = "aa", p2 = "a*";

    Solution sol;

    cout << (sol.isMatch(s1, p1) == 1 ? "true" : "false") << endl;
    cout << (sol.isMatch(s2, p2) == 1 ? "true" : "false") << endl;

    return 0;
}